package cn.arnold.offer.xiaohs;

import java.util.ArrayList;
import java.util.Collections;
import java.util.List;

public class Main {
    public static void main(String[] args) {
        String s = "abaccd";
        System.out.println(solution(s));

    }

    static int solution(String s) {
        boolean[][] dp = new boolean[s.length()][s.length()];
        List<List<String>> ans = new ArrayList<List<String>>();
        int length = s.length();
        for (int k = 1; k <= length; k++) {
            for (int i = 0; i <= length - k; i++) {
                dp[i][i + k - 1] = s.charAt(i) == s.charAt(i + k - 1) && (k < 3 || dp[i + 1][i + k - 1 - 1]);
            }
        }
        helper(s, 0, dp, new ArrayList<String>(), ans);
        List<Integer> listLen = new ArrayList<Integer>();
        for (List<String> e : ans) {
            listLen.add(e.size());
        }
        Collections.sort(listLen);
        return listLen.get(0);
    }

    //回溯
    static void helper(String s, int start, boolean[][] dp, List<String> temp, List<List<String>> res) {
        if (start == s.length()) {
            res.add(new ArrayList<String>(temp));
        }
        for (int i = start; i < s.length(); i++) {
            if (dp[start][i]) {
                String left = s.substring(start, i + 1);
                temp.add(left);
                helper(s, i + 1, dp, temp, res);
                temp.remove(temp.size() - 1);
            }
        }
    }
}
